package leetcode.code0403;

/**
 * 从哪能到这来 <br>
 *
 *
 * @author CaoYu
 * @date 2021年10月5日
 * @description
 */
public class Solution3 extends Solution403 {

	@Override
	public boolean canCross(int[] stones) {
		if (stones[1] != 1)
			return false;
		if (stones.length == 2)
			return true;
		int len = stones.length;
		Boolean[][] dp = new Boolean[len][len];
		return this.canCross(stones, 1, 1, len - 1, dp);// 当前位置,抵达当前位置的k,能否到达最后
	}

	private boolean canCross(int[] stones, int k, int first, int last, Boolean[][] dp) {
		if (first == last) {
			return true;
		}
		if (dp[k][first] != null)
			return dp[k][first];
		for (int i = k - 1; i <= k + 1; i++) {
			int to = stones[first] + i;
			for (int j = first + 1; j <= last && stones[j] <= to; j++) {
				if (stones[j] == to) {
					if (this.canCross(stones, i, j, last, dp)) {
						dp[k][first] = true;
						return true;
					}
				}
			}
		}
		dp[k][first] = false;
		return false;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
